package TopK;
import java.util.Arrays;
import java.util.Collections;
import java.util.Vector;

import Circuit.*;


public class TopKAlgo 
{
	
	
	/*************************************************************************************************************/
	/** Title: GetChildrenTrees																					
	/** Description: Returns a vector of the derivation trees of all children of a circuit node														
	/*************************************************************************************************************/
	
	public static Vector<DerivationTree> GetChildrenTrees (CircuitNode orNode)
	{
		Vector<DerivationTree> treeArr = new Vector<DerivationTree>();
		
		for (CircuitNode child : orNode.getChildren()) //can delete all "AND" nodes because every later node will have sons from "OR" node only 
		{
			treeArr.addAll(child.getTrees());
			((CircuitNode)child).getTrees().clear();
		}
		
        return treeArr;
    }
	
	
	/*************************************************************************************************************/
	/** Title: GetChildrenTreeVectors																					
	/** Description: Returns a vector of the derivation trees of all children of a circuit node														
	/*************************************************************************************************************/
	
	public static Vector<Vector<DerivationTree>> GetChildrenTreeVectors (CircuitNode andNode)
	{
		int n = andNode.getChildren().size();
		Vector<Vector<DerivationTree>> childrenTrees = new Vector<Vector<DerivationTree>>();
		
		for (int j = 0; j < n; j++) 
		{
			childrenTrees.add(andNode.getChildren().elementAt(j).getTrees());
		}
        
        return childrenTrees;
    }
	
	

	/*************************************************************************************************************/
	/** Title: Handle_OR_Node																					
	/** Description: Handles OR type node in the circuit														
	/*************************************************************************************************************/
	
	public static Vector<DerivationTree> Handle_OR_Node (CircuitNode orNode, int k)
	{
		Vector<DerivationTree> treeArr = GetChildrenTrees(orNode);
		Collections.sort(treeArr); //sort in descending order
        return (treeArr.size() > k) ? SubVector(treeArr, 0 , k) : treeArr;
    }
	
	
	
	/*************************************************************************************************************/
	/** Title: SubVector																						 
	/** Description: Returns a sub vector of the input vector, starting from start index until end index		
	/*************************************************************************************************************/
	
	public static Vector<DerivationTree> SubVector (Vector<DerivationTree> vector, int start, int end)
	{
		Vector<DerivationTree> subVector = new Vector<DerivationTree>();
		for (int i = start; i < end; i++) 
		{
			subVector.add( vector.get(i) );
		}
		
		return subVector;
	}
	
	
	/*************************************************************************************************************/
	/** Title: Handle_AND_Node																					
	/** Description: Handles AND type node in the circuit														
	/*************************************************************************************************************/
	
	public static Vector<DerivationTree> Handle_AND_Node (CircuitNode circuitNode, int k)
	{
		Vector<Vector<DerivationTree>> arr = GetChildrenTreeVectors(circuitNode);
		ComparissonTree.CompareNode root = new ComparissonTree.CompareNode();
		int [] indeices = new int[arr.size()];
		Arrays.fill(indeices, 0);
		root.setIndices(indeices);
		
		ComparissonTree T = new ComparissonTree (root);
		Vector<DerivationTree> treeArr = new Vector<DerivationTree>();
        ComparissonTree.CompareNode chosenNode = new ComparissonTree.CompareNode();
        
        for (int i = 0; i < k; i++) 
        {
			for (ComparissonTree.CompareNode u : T.getLeaves())
			{
				InitializeCompareNode(arr, u, circuitNode);
			}
			
			// select the best node of the leaves
			chosenNode = T.getLeaves().get(0);
			treeArr.add(chosenNode.getTree());
            T.BuildLeaves(chosenNode);
		}
        
        return treeArr;
	}
	
	
	
	/*************************************************************************************************************/
	/** Title: InitializeCompareNode																			
	/** Description: Initialize the parameters of CompareNode for  AND type CompareNode							
	/*************************************************************************************************************/
	
	public static void InitializeCompareNode (Vector<Vector<DerivationTree>> arr, ComparissonTree.CompareNode v, CircuitNode circuitNode) 
	{
		DerivationTree curTree = new DerivationTree();
		double weight = circuitNode.getRuleUsed().getWeight();
		
		for (int i = 0; i < arr.size(); i++) 
		{
			if (arr.get(i).size() > v.getIndices()[i])
			{
				weight *= arr.get(i).get( v.getIndices()[i] ).getWeight();
				curTree.addFactPointer(arr.get(i).get( v.getIndices()[i] ).getDerivedFact());
				curTree.addChild(arr.get(i).get( v.getIndices()[i] ));
				arr.get(i).get( v.getIndices()[i] ).addParent(curTree);
			}
		}
		
		curTree.setWeight(weight);
		curTree.setDerivedFact(circuitNode);		
		v.setTree(curTree);
	}
	
	
	
	/*************************************************************************************************************/
	/** Title: CiruitTopKAlgo																					
	/** Description: Updates Top-k derivation trees for a node in the circuit									
	/*************************************************************************************************************/
	
	public static CircuitNode QueryTopKOneNode (CircuitNode v, int k)
	{
		if ( false == v.isFact() && false == v.isTopKUpdated() )
		{
			for ( CircuitNode child : v.getChildren() ) 
			{
				QueryTopKOneNode(child, k);
			}
			
			if (v.getType().equals( "OR" ))
			{		
				v.setTrees(Handle_OR_Node(v, k));
			}
		
			else if (v.getType().equals( "AND" ))
			{	        
				v.setTrees(Handle_AND_Node(v, k));
			}
				
			v.setTopKUpdated(true);
		}

		return v;
	}
	
	
	/*************************************************************************************************************/
	/** Title: CiruitTopKAlgoBottomUp																			
	/** Description: Updates Top-k derivation trees for all nodes in the circuit								
	/*************************************************************************************************************/
	
	/*public static void CiruitTopKAlgoBottomUp (TopKTree T, Circuit C, int k)
	{
		Vector<CircuitNode> curLayer = (Vector)C.getFacts().clone();
		Vector<CircuitNode> nextLayer = new Vector<CircuitNode>();
		int layerNum = 1;
		int numOfAndKNodes = 0;
		int numOfOrKNodes = 0;
		int numOfFacts = 0;
		while (0 != curLayer.size())
		{
			for (CircuitNode v : curLayer) 
			{
				if ( false == v.IsTopKUpdated() )
				{
					if (v.getType().equals( "OR" ))
					{
						numOfOrKNodes++;
						v.setTrees(Handle_OR_Node(v, k));
					}
				
					else if (v.getType().equals( "AND" ))
					{
						numOfAndKNodes++;
						v.setTrees(Handle_AND_Node(v, k));
					}
					
					else
					{
						numOfFacts++;
					}
					
					if (0 == v.getParents().size()v.getType() == "fact") //for querying
					{
						T.addDerivation(v.getTrees());
					}
					
					v.SetTopKUpdate(true);
				}
				
				AddParentsToNextLayer(nextLayer, v, layerNum);
			}
			
			layerNum++;
			curLayer.clear();
			curLayer = (Vector)nextLayer.clone();
			nextLayer.clear();
		}
		C.numOfNodes = (numOfOrKNodes + numOfFacts + numOfAndKNodes) * (k + 1);
		T.setNumOfTreeNodes((numOfOrKNodes + numOfFacts) * k);
	}*/
		
	
	
	/*************************************************************************************************************/
	/** Title: AddParentsToNextLayer																			
	/** Description:  		 													
	/*************************************************************************************************************/
	
	/*public static void AddParentsToNextLayer (Vector<CircuitNode> nextLayer, CircuitNode v, int layerNum)
	{
		for (CircuitNode parent : v.getParents()) 
		{
			if (parent.getLevel() == layerNum) 
			{
				nextLayer.add(parent);
				if (parent.getType() == "AND" && false == nextLayer.contains(parent.getParents().get(0)))// AND node should have only one parent: OR node 
				{
					nextLayer.add((CircuitNode)parent.getParents().get(0));
				}
				
				if (true == nextLayer.contains(parent.getParents().get(0))) //make sure that OR node is the last 
				{
					nextLayer.remove(nextLayer.indexOf(parent.getParents().get(0)));
					nextLayer.add(parent.getParents().get(0));
				}
			}
		}										
	}*/
	
	
	/*************************************************************************************************************/
	/** Title: DuplicateDerivTreesForFacts																			
	/** Description: Duplicate Derivation Tree of each fact k times 		 													
	/*************************************************************************************************************/
	
	/*public static void DuplicateDerivTreesForFacts (Circuit C, int k)
	{
		for (Circuit.CircuitNode fact : C.getFacts()) 
		{
			Vector<DerivationTree> derivTreesOfFact = new Vector<DerivationTree>();
			for (int i = 0; i < k; i++) 
			{
				derivTreesOfFact.add(fact.getTrees().get(0));
			}
			
			fact.setTrees(derivTreesOfFact);
		}
	}*/
	
	
	
	/*************************************************************************************************************/
	/** Title: ActivateTopKOnCircuit																			
	/** Description: Print all trees of Circuit inputed		 													
	/*************************************************************************************************************/
	
	/*public static void ActivateTopKOnCircuit (TopKTree T, Circuit C, int k, int recursionDepth)
	{
		DuplicateDerivTreesForFacts(C, k);
		CiruitTopKAlgoBottomUp(T, C, k);
	}*/
	
	
	
	/*************************************************************************************************************/
	/** Title: CleanCircuit																			
	/** Description: 		 													
	/*************************************************************************************************************/
	
	/*public static void CleanCircuit (Circuit C)
	{
		Vector<CircuitNode> curLayer = (Vector)C.getFacts().clone();
		Vector<CircuitNode> nextLayer = new Vector<CircuitNode>();
		int layerNum = 1;
		while (0 != curLayer.size())
		{
			for (CircuitNode v : curLayer) 
			{
				if (v.getType() != "fact") 
				{
					v.getTrees().clear();
					v.SetTopKUpdate(false);
				}
				
				AddParentsToNextLayer(nextLayer, v, layerNum);
			}
			
			layerNum++;
			curLayer.clear();
			curLayer = (Vector)nextLayer.clone();
			nextLayer.clear();
		}
	}*/
}